Problema computacional

En ciencia computacional teórica, un problema computacional o problema abstracto es una relación entre un conjunto de instancias y un conjunto de soluciones. Un problema abstracto permite establecer formalmente la relación deseada entre cada instancia del problema y su correspondiente solución. Una solución algorítmica a un problema abstracto consiste de un algoritmo que por cada instancia del problema calcula al menos una solución correspondiente –en caso de haberla– o expide un certificado de que no existe solución alguna. Un problema abstracto se convierte en un problema concreto cuando las instancias y soluciones están codificadas en forma de lenguajes formales.

Los problemas abstractos suelen definirse en dos partes: en la primera se describe al conjunto de instancias y en la segunda se describe la solución esperada para cada instancia. Por ejemplo, el problema de ordenación de números enteros se suele definir como sigue:

Instancia: Una sucesión finita de números enteros ${\displaystyle \left(a_{1},a_{2},\ldots ,a_{n}\right)}$

Solución: Una permutación ${\displaystyle \left(a_{1}^{\prime },a_{2}^{\prime },\ldots ,a_{n}^{\prime }\right)}$ de la sucesión de entrada tal que ${\displaystyle a_{1}^{\prime }\leq a_{2}^{\prime }\leq \cdots \leq a_{n}^{\prime }}$

Aquí tanto el conjunto de instancias y el de soluciones es el mismo, pues se trata del conjunto de todas las sucesiones finitas de números enteros. La relación que hay entre ellos asigna a cada sucesión ${\displaystyle \left(a_{1},a_{2},\ldots ,a_{n}\right)}$ la única permutación ${\displaystyle \left(a_{1}^{\prime },a_{2}^{\prime },\ldots ,a_{n}^{\prime }\right)}$ tal que ${\displaystyle a_{1}^{\prime }\leq a_{2}^{\prime }\leq \cdots \leq a_{n}^{\prime }}$. Por ejemplo, ${\displaystyle \left(6,9,4,5\right)}$ tiene como solución a ${\displaystyle \left(4,5,6,9\right)}$. Una solución algorítmica al problema de ordenamiento es el ordenamiento de burbuja porque este algoritmo produce una solución como salida cada vez que se le suministra una instancia como entrada.